package leet;

import common.TreeNode;
import common.Util;
import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 2018/5/9 10:29
 */
public class Array {

    // if (nums == null || nums.length < 1) return null;

    /**
     * 1. 两数之和
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                res[0] = map.get(nums[i]);
                res[1] = i;
                return res;
            } else {
                map.put(target - nums[i], i);
            }
        }
        return res;
    }


    /**
     * 268. 缺失数字
     * 求和相减
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return (1 + n) * n / 2 - sum;
    }

    /**
     * 64. 最小路径和
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length < 1 || grid[0].length < 1) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 561. 数组拆分 I
     * ps:贪心，想要最大，必须相邻的一组损失才最小。
     * @param nums
     * @return
     */
    public int arrayPairSum(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < nums.length; i += 2) {
            res += nums[i];
        }
        return res;
    }

    /**
     * 169. 求众数
     * 1.sort 2.投票法
     * @param nums
     * @return
     */
    public int majorityElementI(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
    public int majorityElementII(int[] nums) {
        int majority = nums[0];
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) {
                majority = nums[i];
                cnt++;
                continue;
            }
            if (nums[i] == majority) {
                cnt++;
            } else {
                cnt--;
            }

        }

        return majority;
    }

    /**
     * 27. 移除元素
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[res++] = nums[i];
            }
        }
        return res;
    }

    /**
     * 66. 加一
     * ps: 用数字做了尝试，都错了，只能用字符串做。心累。。 也没用， again...
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length < 1) {
            return null;
        }
        int res = 0;
        int carry = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (i == digits.length - 1) {
                res = digits[i] + carry + 1;
            } else {
                res = digits[i] + carry;
            }

            if (res > 9) {
                carry = 1;
                res -= 10;
            } else {
                carry = 0;
            }
            digits[i] = res;
        }
        if (carry == 1) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            for (int i = 0,k = 1; i < digits.length;k++, i++) {
                result[k] = digits[i];
            }
            return result;
        }
        return digits;
    }


    /**
     * 88. 合并两个有序数组
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx = m + n - 1;
        m--;
        n--;
        while (n >= 0){
            if (m >= 0 && nums1[m] > nums2[n]){
                nums1[idx--] = nums1[m--];
            } else {
                nums1[idx--] = nums2[n--];
            }
        }
    }

    /**
     * 654. 最大二叉树
     * @param nums
     * @return
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length < 1) {
            return null;
        }
        return constructMaximumBinaryTreeCore(nums,0,nums.length - 1);
    }
    private TreeNode constructMaximumBinaryTreeCore(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        int max = nums[lo];
        int index = lo;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left = constructMaximumBinaryTreeCore(nums,lo,index - 1);
        root.right = constructMaximumBinaryTreeCore(nums,index + 1, hi);
        return root;
    }


    /**
     * 35. 搜索插入位置
     * 1.bf  2.二分 TODO 找第一个大于等于目标值的下标.
     * 坑:重复值.
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }


    /**
     * 283. 移动零
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length < 1) {
            return;
        }
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    /**
     * 121. 买卖股票的最佳时机
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 1) {
            return 0;
        }
        int curMin = prices[0];
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            curMin = Math.min(curMin,prices[i]);
            maxProfit = Math.max(prices[i] - curMin,maxProfit);
        }
        return maxProfit;
    }

    /**
     * 122. 买卖股票的最佳时机 II
     * @param prices
     * @return
     */
    public int maxProfitII(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }

    /**
     * 53. 最大子序和
     * 1.bf 2.贪心
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int maxSum = nums[0];
        int curSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (curSum < 0) {
                curSum = nums[i];
            } else {
                curSum += nums[i];
            }
            if (curSum > maxSum) {
                maxSum = curSum;
            }

        }
        return maxSum;
    }


    /**
     * 73. 矩阵置零
     *
     一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
     一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
     你能想出一个常数空间的解决方案吗？
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] rows = new int[m];
        int[] cols = new int[n];
        Arrays.fill(rows,1);
        Arrays.fill(cols,1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = 0;
                    cols[j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rows[i] == 0 || cols[j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
    }


    /**
     * 34. 搜索范围
     * 二分找第一个,最后一个位置
     *坑: 没有考虑不存在的情况.
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length < 1) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        res[0] = findFirstIndex(nums,target);
        res[1] = findLastIndex(nums,target);
        return res;
    }
    private int findFirstIndex(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
             if (nums[mid] > target){
                hi = mid - 1;
            } else if (nums[mid] < target){
                lo = mid + 1;
             } else if (mid != 0 && nums[mid] == target && nums[mid - 1] == target) {
                hi = mid - 1;
            } else {
                 return mid;
            }
        }
        return -1;
    }
    private int findLastIndex(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
             if (nums[mid] > target){
                hi = mid - 1;
            } else if (nums[mid] < target){
                lo = mid + 1;
            } else if (mid != nums.length - 1 && nums[mid] == target && nums[mid + 1] == target) {
                lo =  mid + 1;
            } else {
                 return mid;
             }
        }
        return -1;
    }

    /**
     *
     *62. 不同路径
     * 1. dp 2.math todo
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        if (m < 1 || n < 1) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 63. 不同路径 II
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        if (dp[0][0] == 0 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else if (i == 0) {
                    if (j > 0) {
                        dp[i][j] = dp[i][j - 1];
                    }
                } else if (j == 0) {
                    if (i > 0) {
                        dp[i][j] = dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }


    /**
     *643. 子数组最大平均数 I
     * 1.bf...  ...
     * @param nums
     * @param k
     * @return
     */
    public double findMaxAverage(int[] nums, int k) {
        if (nums == null || nums.length < 1 || k < 1) {
            return 0;
        }
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        double res = sum;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            res = Math.max(res,sum);
        }
        return res / k;
    }


    /**
     * 217. 存在重复元素
     * 1. sort 2.hashmap
     * @param nums
     * @return
     */
    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length < 1) {
            return false;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 75. 分类颜色
     * @param nums
     */
    public void sortColorsI(int[] nums) {
        int zeroCnt = 0;
        int oneCnt = 0;
        int twoCnt = 0;
        for (int i = 0; i < nums.length; i++) {
            switch (nums[i]) {
                case 0:zeroCnt++;break;
                case 1:oneCnt++;break;
                case 2:twoCnt++;break;
            }
        }
        int index = 0;
        while (zeroCnt-- > 0) {
            nums[index++] = 0;
        }
        while (oneCnt-- > 0) {
            nums[index++] = 1;
        }
        while (twoCnt-- > 0) {
            nums[index++] = 2;
        }
    }
    public void sortColorsII(int[] nums) {
        int zero = 0;
        int two = nums.length - 1;
        int cur = 0;
        while (cur <= two) {

            if (nums[cur] == 0) {
                nums[cur] = nums[zero];
                nums[zero] = 0;
                zero++;
            }
            if (nums[cur] == 2) {
               nums[cur] = nums[two];
               nums[two] = 2;
               two--;
               cur--;
            }
            cur++;
        }

        }

    public void sortColorsIII(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        int i = 0;
        while (i <= hi) {
            if (nums[i] == 0) {
                Util.swap(nums,lo++,i++);
            } else if (nums[i] == 2) {
                Util.swap(nums,i,hi--);
            } else {
                i++;
            }
        }
    }
    public void sortColorsIV(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        int i = 0;
        while (i <= hi) {
            if (nums[i] == 0) {
                Util.swap(nums,lo,i);
                lo++;
            } else if (nums[i] == 2) {
                Util.swap(nums,i,hi--);
                i--;
            }
            i++;
        }
    }
    /**
     * 120. 三角形最小路径和
     * 我的像狗屎一样。。。
     * @param triangle
     * @return
     */
    public int minimumTotalMine(List<List<Integer>> triangle) {
        if (triangle == null) {
            return 0;
        }
        List<List<Integer>> dp = new ArrayList<>();
        dp.add(new ArrayList<>(triangle.get(0).get(0)));
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> cur = new ArrayList<>();
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (j == 0) {
                    cur.add(triangle.get(i).get(j) + triangle.get(i - 1).get(j));
                } else if (j == triangle.get(i).size() - 1){
                    cur.add(triangle.get(i).get(j) + triangle.get(i - 1).get(j - 1));
                } else {
                    cur.add(Math.min(triangle.get(i - 1).get(j - 1),triangle.get(i - 1).get(j)) + triangle.get(i).get(j));
                }
            }
            dp.add(cur);
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < dp.get(dp.size() - 1).size(); i++) {
            res = Math.min(res,dp.get(dp.size() - 1).get(i));
        }
        return res;
    }
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j],dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
    @Test
    public void test() {
        int[] a1 = {2,1,2,1,0,0,2,1};
        sortColorsIV(a1);
        for (int i = 0; i < a1.length; i++) {
            System.out.print(a1[i] + " ");
        }
       /* int[] nums = {-1,-2};
        System.out.println(findMaxAverage(nums,1));*/
       // System.out.println(uniquePaths(7,3));
        /*int[] a1 = {5,7,7,8,8,10};
        System.out.println(findFirstIndex(a1,6));
         System.out.println(findLastIndex(a1,6));*/

        /*int[][] a = {{1},{0}};
        setZeroes(a);*/
        /*moveZeroes(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }*/
        /*System.out.println(searchInsert(a,5));
        System.out.println(searchInsert(a,2));
        System.out.println(searchInsert(a,7));*/
        /*int[][] grid = {
                {1,3,1},
                {1,5,1},
                {4,2,1}
    };
        System.out.println(minPathSum(grid));*/
        /*int[] a1 = {3,0,1};
        int[] a2 = {1};
        System.out.println(missingNumber(a1));*/
        /*merge(a1,0,a2,1);
        for (int i = 0; i < a1.length; i++) {
            System.out.print(a1[i] + " ");
        }*/
        /*System.out.println();
        int[] num = {7,2,8,5,0,9,1,2,9,5,3,6,6,7,3,2,8,4,3,7,9,5,7,7,4,7,4,9,4,7,0,1,1,1,7,4,0,0,6};
        int[] res = plusOne(num);
        System.out.println(Arrays.toString(res));*/
        /*int res = removeElement(num, 1);
        for (int i = 0; i < res; i++) {
            System.out.print(num[i] + " ");
        }*/
    }
}
